package com.github.hgkmail.hello.leetcode101.dualpointer;

/**
 * https://leetcode.cn/problems/valid-palindrome-ii
 * 这道题的难点是需要考虑2种可能：删除左边的字符、删除右边字符
 */
public class LC680ValidPalindrome2 {
    //单纯判断回文
    public boolean isPalindrome(char[] arr, int begin, int end) {
        int i=begin;
        int j=end;
        while (i<j) {
            if (arr[i]==arr[j]) {
                i++;
                j--;
                continue;
            }
            return false;
        }
        return true;
    }

    public boolean validPalindrome(String s) {
        //转成char array
        char[] arr = s.toCharArray();
        //base case
        if (arr.length<=1) {
            return true;
        }
        //双指针
        int i=0;
        int j=arr.length-1;
        while (i<j) {
            if (arr[i]==arr[j]) {
                i++;
                j--;
                continue;
            }
            //尝试删除左边或右边
            return isPalindrome(arr,i+1,j) || isPalindrome(arr, i,j-1);
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println(new LC680ValidPalindrome2()
                .validPalindrome("aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"));
    }
}
